﻿// 4196. 最短路径.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/4199/

给定一个 n
 个点 m
 条边的的无向图。

点的编号从 1
 到 n
。

图中可能包含重边和自环。

请你找到并输出一条从点 1
 到点 n
 的最短路径。

输入格式
第一行包含两个整数 n,m
。

接下来 m
 行，每行包含三个整数 a,b,w
，表示点 a
 和点 b
 之间存在一条无向边，边长为 w
。

输出格式
如果最短路径不存在，则输出 −1
。

否则，在一行内输出从点 1
 到点 n
 的最短路径中依次包含的点的编号，各点编号之间用空格隔开。

如果答案不唯一，输出任意合理方案均可。

数据范围
前六个测试点满足 2≤n≤10
，1≤m≤10
。
所有测试点满足 2≤n≤105
，1≤m≤105
，1≤a,b≤n
，1≤w≤106
。
本题不卡spfa算法。

输入样例：
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
输出样例：
1 4 3 5
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 